package backTrack;

import java.util.*;

/**
 * 回溯记得画树，一般都是一层for，代表某一层
 */

public class ds51_n_queue {
    public static void main(String[] args) {
        System.out.println(solveNQueens(4));
    }
    public static List<List<String>> solveNQueens(int n) {
        List<List<String>> ans = new ArrayList<>();
        char[][] queue = new char[n][n];
        for (int i = 0; i < n; i++) {
            Arrays.fill(queue[i],'.');
        }
        dfs(ans, queue, 0);
        return ans;
    }
    public static void dfs(List<List<String>> ans, char[][] queue, int n){
        if(n == queue.length){
            List<String> list = new ArrayList<>();
            for (int i = 0; i < queue.length; i++) {
                StringBuilder stringBuilder = new StringBuilder();
                for (int j = 0; j < queue.length; j++) {
                    stringBuilder.append(queue[i][j]);
                }
                list.add(String.valueOf(stringBuilder));
            }
            ans.add(new ArrayList<>(list));
            return;
        }
        for (int j = 0; j < queue.length; j++) {
            if(queue[n][j] == '.' && isValid(n, j, queue)){
                queue[n][j] = 'Q';
                dfs(ans, queue, n + 1);
                queue[n][j] = '.';
            }
        }
    }
    public static boolean isValid(int index, int j_index, char[][] queue){
        for (int i = 0; i < queue.length; i++) {
            if(queue[index][i] == 'Q')
                return false;
        }

        for (int i = 0; i < queue.length; i++) {
            if(queue[i][j_index] == 'Q')
                return false;
        }
        /**
         * 只需要检查左上和右上对角，右下与左下还没有遍历不用检查
         */
        int i = index, j = j_index;
        while(i >= 0 && j >= 0){
            if(queue[i][j] == 'Q')
                return false;
            i--;
            j--;
        }

        i = index;
        j = j_index;
        while(i >= 0 && j < queue.length){
            if(queue[i][j] == 'Q')
                return false;
            i--;
            j++;
        }
        return true;
    }
}
